1045D - Interstellar battle - CodeForces Solution

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;
const int N = (int)1e5+228;

int n, par[N];
double p[N];
vector<vector<int> > adj;
int q;
double sum[N];

void dfs(int u)
{
    for(int v : adj[u])
    {
        if(v == par[u])
            continue;
        par[v] = u;
        sum[par[v]] += 1.0 - p[v];
        dfs(v);
    }
}

void solve()
{
    cin >> n;
    for(int i=0; i<n; ++i)
        cin >> p[i];

    adj.assign(n+7, vector<int>());
    for(int i=1; i<n; ++i)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0);

    double res = 0;
    for(int i=0; i<n; ++i)
    {
        double tmp = 1.0 - p[i];
        if(i != 0)
            tmp *= p[par[i]];
        res += tmp;
    }
    cin >> q;
    while(q--)
    {
        int u;
        cin >> u;
        double tmp = 1.0 - p[u];
        if(u != 0)
            tmp *= p[par[u]], sum[par[u]] -= 1.0 - p[u];
        res -= tmp;
        res -= p[u] * sum[u];

        cin >> p[u];
        tmp = 1.0 - p[u];
        if(u != 0)
            tmp *= p[par[u]], sum[par[u]] += 1.0 - p[u];
        res += tmp;
        res += p[u] * sum[u];
        
        cout << fixed << setprecision(6) << res << '\n';

    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
    #endif // ONLINE_JUDGE
    solve();
    //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}